• 什么是数组❓

  数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。数据是线性表。

  而与它相对立的概念是非线性表，比如二叉树、堆、图等。之所以叫非线性，是因为，在非线性表中，数据之间并不是简单的前后关系。

  数组使用连续的空间进行存储，这样便可以支持随机访问

• 🔥 数组为什么可以支持随机访问?

  计算机会记住数组的出示内存地址，而又因为内存地址的连续性，这样便可根据初始地址计算出其他元素的内存地址。
  因为需要保持数组的连续性，所以在插入元素和删除元素的时候，就相应变得特别低效。

• 🔥 数组可以用来实现哪些其他的数据结构?

  数据可以用来实现栈、队列、堆。

• 🔥 怎样将数组的插入和删除操作都退化为 O（1）的操作?

  在数组是无序的情况下，在数组插入元素 x 时，可以使用替换的方法，将插入位置的元素替换为 x, 而将原本位置上的元素移动到最后一位元素。

  在元素删除时，在删除了元素之后可以先标记元素为删除状态，而不进行真正的删除，只有当数组没有剩余空间时，再进行一次统一的删除操作。